#include <cstdio>
#include <vector>
#include <list>
#include <algorithm>
#include <deque>
#include <iostream>
#include <fstream>

using namespace std;

struct Code{
	Code(char c, int f):ch(c), freq(f){};
	char ch;
	int freq;
};

struct Node{
	Node():left(NULL),right(NULL){};
	Node(int f, char c='\0'):left(NULL),right(NULL),freq(f),ch(c){};

	Node* left;
	Node* right;
	int freq;
	char ch;

  string encoding;
  
	string to_str(){
		char str[100];
		if(this->ch){
			sprintf(str,"%d %c %s",this->freq,this->ch, this->encoding.c_str());
		}else{
			sprintf(str,"%d",this->freq);
		}
		return string(str); 
	};
};

Node* del_min(list<Node*>& forest){

	if(forest.empty())
		return NULL;

	list<Node*>::iterator min_iter = forest.begin();
	int min_freq = (*min_iter)->freq;

	for(list<Node*>::iterator i=forest.begin(); i!= forest.end(); ++i){
		if((*i)->freq < min_freq){
			min_iter = i;
			min_freq = (*min_iter)->freq;
		}
	}

	Node* min = *min_iter;
	forest.erase(min_iter);
	return min;
}


Node* Huffman_coding(const vector<Code> &codes){
	list<Node*> forest;

	for(vector<Code>::const_iterator i=codes.begin(); i!= codes.end(); ++i){
		forest.push_back(new Node(i->freq, i->ch));
	}

	while(forest.size()>1){
		Node* min1 = del_min(forest);
		Node* min2 = del_min(forest);
		
		Node* p = new Node(min1->freq+min2->freq);
		p->left=min1;
		p->right=min2;
		forest.push_back(p);
	}

	Node* root = *(forest.begin());
	return root;
}


void output_gv(Node* root, const char* filename){
  ofstream out;
  out.open (filename);

  out << "digraph huffmantree {\n";

  deque<Node*> q;
  q.push_back(root);

  while(!q.empty()){
	  Node* node = q.front();
	  q.pop_front();

	  if(node->left){
		  out<<'"'<<node->to_str().c_str() <<'"' <<" -> ";
		  out<<'"'<<node->left->to_str().c_str()<<'"' <<";\n";
		  q.push_back(node->left);
	  }

	  if(node->right){
		  out<<'"'<<node->to_str().c_str() <<'"' <<" -> ";
		  out<<'"'<<node->right->to_str().c_str()<<'"' <<";\n";
		  q.push_back(node->right);
	  }
  }

  out << "}\n";
  out.close();
}

void calculate_coding(Node* root){
  deque<Node*> q;
  q.push_back(root);

  while(!q.empty()){
	  Node* node = q.front();
	  q.pop_front();

	  if(node->left){
           node->left->encoding = node->encoding + '0';
           q.push_back(node->left);
	  }

	  if(node->right){
           node->right->encoding = node->encoding + '1';
           q.push_back(node->right);
	  }
  }
}

int main(){
	vector<Code> codes;
	codes.push_back(Code('a',5));
	codes.push_back(Code('b',6));
	codes.push_back(Code('c',15));
	codes.push_back(Code('d',52));
	codes.push_back(Code('e',59));
	codes.push_back(Code('f',68));
	codes.push_back(Code('g',78));
	codes.push_back(Code('h',21));
	codes.push_back(Code('i',32));
	codes.push_back(Code('j',24));

	Node* root = Huffman_coding(codes);
	calculate_coding(root);
	output_gv(root,"huffman.gv");
	return 0;
}
